package leetcode.D100.T95;

import util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-16 15:22:53 星期三
 */

class Solution {

    private int k = 1;

    public List<TreeNode> generateTrees(int n) {
        Map<Integer, List<TreeNode>> map = new HashMap<>();
        map.put(0, new ArrayList<TreeNode>());
        map.get(0).add(null);
        List<TreeNode> tempList = new ArrayList<>();
        tempList.add(new TreeNode());
        map.put(1, tempList);
        for (int i=2; i<=n; ++i) {
            List<TreeNode> list = new ArrayList<>();
            for (int j=1; j<=i; ++j) {
                List<TreeNode> leftList = map.get(j-1);
                List<TreeNode> rightList = map.get(i-j);
                for (TreeNode left : leftList) {
                    for (TreeNode right : rightList) {
                        TreeNode root = new TreeNode();
                        root.left = left;
                        root.right = right;
                        list.add(root);
                    }
                }
            }
            map.put(i, list);
        }
        List<TreeNode> roots = map.get(n);
        List<TreeNode> res = new ArrayList<>();
        for (TreeNode root : roots) {
            k = 1;
            res.add(inorder(root));
        }
        return res;
    }

    private TreeNode inorder(TreeNode root) {
        if (root == null)
            return null;
        TreeNode t = new TreeNode();
        t.left = inorder(root.left);
        t.val = k++;
        t.right = inorder(root.right);
        return t;
    }
}